package leetcode.code0188;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 执行用时：6 ms, 在所有 Java 提交中击败了56.77%的用户
 *
 * 内存消耗：38.2 MB, 在所有 Java 提交中击败了28.80%的用户
 *
 * 通过测试用例：211 / 211
 */
public class Solution1 implements IDebug {

	public int maxProfit(int k, int[] prices) {
		int len = prices.length;
		if (k == 0 || len < 2)
			return 0;
		k = Math.min(k, len >> 1);
		int[][] dp = new int[len + 1][k + 1];// d[i][j]截至第i天做了j次交易，最大收入是多少
		int[] maxs = new int[k + 1];
		for (int i = 0; i <= k; i++) {
			maxs[i] = Integer.MIN_VALUE;
		}
		for (int i = 2; i <= len; i++) {
			for (int j = 1; j <= k; j++) {
				maxs[j] = Math.max(dp[i - 2][j - 1] - prices[i - 2], maxs[j]);
				dp[i][j] = Math.max(prices[i - 1] + maxs[j], dp[i - 1][j]);
			}
		}
		return dp[len][k];
	}

	public int maxProfit3(int k, int[] prices) {
		int len = prices.length;
		if (k == 0 || len < 2)
			return 0;
		k = Math.min(k, len >> 1);
		int[][] dp = new int[len + 1][k + 1];// d[i][j]截至第i天做了j次交易，最大收入是多少
		for (int j = 1; j <= k; j++) {
			for (int i = 2; i <= len; i++) {
				int max = Integer.MIN_VALUE;
				for (int m = 1; m < i; m++) {
					max = Math.max(dp[m - 1][j - 1] - prices[m - 1], max);
				}
				dp[i][j] = Math.max(prices[i - 1] + max, dp[i - 1][j]);
			}
		}
		return dp[len][k];
	}

	public int maxProfit2(int k, int[] prices) {
		int len = prices.length;
		if (k == 0 || len < 2)
			return 0;
		k = Math.min(k, len >> 1);
		int[][] dp = new int[len + 1][k + 1];// d[i][j]截至第i天做了j次交易，最大收入是多少
		for (int j = 1; j <= k; j++) {
			for (int i = 2; i <= len; i++) {
				int max = dp[i - 1][j];
				for (int m = 1; m < i; m++) {
					max = Math.max(prices[i - 1] - prices[m - 1] + dp[m - 1][j - 1], max);
				}
				dp[i][j] = max;
			}
		}
		return dp[len][k];
	}

	public int maxProfit9(int k, int[] prices) {
		int len = prices.length;
		if (k == 0 || len < 2)
			return 0;
		k = Math.min(k, len >> 1);
		int[][] dp = new int[len + 1][len + 1];
		for (int i = 2; i <= len; i++) {
			int cur = prices[i - 1];
			int min = Integer.MAX_VALUE;
			for (int m = i - 1; m >= 1; m--) {
				int last = prices[m - 1];
				min = Math.min(min, last);
				dp[m][i] = Math.max(cur - min, dp[m][i - 1]);
			}
		}
//		H.printObject(dp);
		int res = 0;
		int[][] ans = new int[len + 1][k + 1];
		for (int i = 2; i <= len; i++) {// 第i天开始做最后一笔交易
			for (int j = 1; j <= k; j++) {
				int max = ans[i - 1][j - 1] + dp[i][len];
				max = Math.max(max, ans[i - 1][j]);
				res = Math.max(res, max);
				ans[i][j] = max;
			}
		}
		HelpDebug.print(ans);
		return res;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(2, this.maxProfit(2, HelpDebug.str2array3("[2,4,1]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(8, this.maxProfit(1, HelpDebug.str2array3("[3,2,6,5,3,10]")));

		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		HelpDebug.compare(11, this.maxProfit(2, HelpDebug.str2array3("[3,2,6,5,3,10]")));

		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
